#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;

// 综合示例1：LeetCode 15 - 三数之和（双指针 + 排序）
class ThreeSumComprehensive {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size() - 2; i++) {
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            // 双指针查找两数之和
            int left = i + 1, right = nums.size() - 1;
            int target = -nums[i];
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    
                    // 跳过重复元素
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
};

// 综合示例2：LeetCode 200 - 岛屿数量（DFS）
class IslandsDFS {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1') {
            return;
        }
        
        grid[i][j] = '0'; // 标记为已访问
        
        // 四个方向递归
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

// 综合示例3：LeetCode 200 - 岛屿数量（BFS）
class IslandsBFS {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    void bfs(vector<vector<char>>& grid, int startX, int startY) {
        queue<pair<int,int>> q;
        q.push({startX, startY});
        grid[startX][startY] = '0';
        
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                
                if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1') {
                    grid[nx][ny] = '0';
                    q.push({nx, ny});
                }
            }
        }
    }
};

// 综合示例4：LeetCode 3 - 最长无重复字符子串（滑动窗口/双指针）
class LongestSubstring {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> charMap(128, -1);
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s[right];
            
            // 如果字符已存在且在当前窗口内
            if (charMap[c] >= left) {
                left = charMap[c] + 1;
            }
            
            charMap[c] = right;
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

// 综合示例5：LeetCode 127 - 单词接龙（BFS）
class WordLadderBFS {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        
        queue<string> q;
        q.push(beginWord);
        
        int length = 1;
        
        while (!q.empty()) {
            int size = q.size();
            
            for (int i = 0; i < size; i++) {
                string current = q.front();
                q.pop();
                
                if (current == endWord) {
                    return length;
                }
                
                // 尝试改变每个字符
                for (int j = 0; j < current.length(); j++) {
                    char original = current[j];
                    
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        
                        current[j] = c;
                        
                        if (wordSet.find(current) != wordSet.end()) {
                            q.push(current);
                            wordSet.erase(current);
                        }
                    }
                    
                    current[j] = original;
                }
            }
            
            length++;
        }
        
        return 0;
    }
};

// 综合示例6：LeetCode 46 - 全排列（DFS回溯）
class PermutationsDFS {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        
        backtrack(nums, path, used, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, path, used, result);
            path.pop_back();
            used[i] = false;
        }
    }
};

// 综合示例7：LeetCode 11 - 盛最多水的容器（双指针）
class ContainerWater {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxWater = 0;
        
        while (left < right) {
            int currentArea = min(height[left], height[right]) * (right - left);
            maxWater = max(maxWater, currentArea);
            
            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
};

// 综合示例8：LeetCode 994 - 腐烂的橘子（多源BFS）
class RottingOrangesBFS {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int,int>> q;
        int fresh = 0;
        
        // 找到所有腐烂的橘子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        
        if (fresh == 0) return 0;
        
        int minutes = 0;
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        while (!q.empty()) {
            int size = q.size();
            bool hasRotten = false;
            
            for (int i = 0; i < size; i++) {
                int x = q.front().first;
            int y = q.front().second;
                q.pop();
                
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        q.push({nx, ny});
                        fresh--;
                        hasRotten = true;
                    }
                }
            }
            
            if (hasRotten) minutes++;
        }
        
        return fresh == 0 ? minutes : -1;
    }
};

// 综合示例9：LeetCode 79 - 单词搜索（DFS回溯）
class WordSearchDFS {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        
        int m = board.size(), n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
        if (index == word.length()) return true;
        
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || 
            board[i][j] != word[index]) {
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = '#'; // 标记为已访问
        
        bool found = dfs(board, word, i + 1, j, index + 1) ||
                    dfs(board, word, i - 1, j, index + 1) ||
                    dfs(board, word, i, j + 1, index + 1) ||
                    dfs(board, word, i, j - 1, index + 1);
        
        board[i][j] = temp; // 恢复
        return found;
    }
};

// 综合示例10：LeetCode 42 - 接雨水（双指针）
class TrappingRainWater {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        
        return water;
    }
};

// 演示函数
void demonstrateComprehensive() {
    cout << "=== 综合算法应用演示 ===" << endl << endl;
    
    // 1. 三数之和（双指针）
    cout << "1. 三数之和（双指针）:" << endl;
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    ThreeSumComprehensive threeSum;
    vector<vector<int>> result = threeSum.threeSum(nums);
    cout << "数组: [-1, 0, 1, 2, -1, -4]" << endl;
    cout << "三数之和为0的组合:" << endl;
    for (const auto& triplet : result) {
        cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "]" << endl;
    }
    cout << endl;
    
    // 2. 岛屿数量（DFS vs BFS）
    cout << "2. 岛屿数量（DFS vs BFS）:" << endl;
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    
    // DFS方法
    vector<vector<char>> gridDFS = grid;
    IslandsDFS islandsDFS;
    int countDFS = islandsDFS.numIslands(gridDFS);
    
    // BFS方法
    vector<vector<char>> gridBFS = grid;
    IslandsBFS islandsBFS;
    int countBFS = islandsBFS.numIslands(gridBFS);
    
    cout << "DFS方法找到的岛屿数量: " << countDFS << endl;
    cout << "BFS方法找到的岛屿数量: " << countBFS << endl << endl;
    
    // 3. 最长无重复字符子串（滑动窗口）
    cout << "3. 最长无重复字符子串（滑动窗口）:" << endl;
    string s = "abcabcbb";
    LongestSubstring longestSub;
    int maxLength = longestSub.lengthOfLongestSubstring(s);
    cout << "字符串: \"" << s << "\"" << endl;
    cout << "最长无重复子串长度: " << maxLength << endl << endl;
    
    // 4. 单词接龙（BFS）
    cout << "4. 单词接龙（BFS）:" << endl;
    string beginWord = "hit";
    string endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    WordLadderBFS wordLadder;
    int ladderLength = wordLadder.ladderLength(beginWord, endWord, wordList);
    cout << "从 \"" << beginWord << "\" 到 \"" << endWord << "\" 的最短转换序列长度: " << ladderLength << endl << endl;
    
    // 5. 全排列（DFS回溯）
    cout << "5. 全排列（DFS回溯）:" << endl;
    vector<int> permNums = {1, 2, 3};
    PermutationsDFS permutations;
    vector<vector<int>> perms = permutations.permute(permNums);
    cout << "数组 [1, 2, 3] 的全排列:" << endl;
    for (const auto& perm : perms) {
        cout << "[";
        for (int i = 0; i < perm.size(); i++) {
            cout << perm[i];
            if (i < perm.size() - 1) cout << ", ";
        }
        cout << "]" << endl;
    }
    cout << endl;
    
    // 6. 盛最多水的容器（双指针）
    cout << "6. 盛最多水的容器（双指针）:" << endl;
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    ContainerWater container;
    int maxArea = container.maxArea(height);
    cout << "高度数组: [1, 8, 6, 2, 5, 4, 8, 3, 7]" << endl;
    cout << "最大面积: " << maxArea << endl << endl;
    
    // 7. 腐烂的橘子（多源BFS）
    cout << "7. 腐烂的橘子（多源BFS）:" << endl;
    vector<vector<int>> oranges = {
        {2, 1, 1},
        {1, 1, 0},
        {0, 1, 1}
    };
    RottingOrangesBFS rottingOranges;
    int minutes = rottingOranges.orangesRotting(oranges);
    cout << "所有橘子腐烂需要的时间: " << minutes << " 分钟" << endl << endl;
    
    // 8. 单词搜索（DFS回溯）
    cout << "8. 单词搜索（DFS回溯）:" << endl;
    vector<vector<char>> board = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };
    string word = "ABCCED";
    WordSearchDFS wordSearch;
    bool found = wordSearch.exist(board, word);
    cout << "在网格中搜索单词 \"" << word << "\": " << (found ? "找到" : "未找到") << endl << endl;
    
    // 9. 接雨水（双指针）
    cout << "9. 接雨水（双指针）:" << endl;
    vector<int> rainHeight = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    TrappingRainWater trappingRain;
    int water = trappingRain.trap(rainHeight);
    cout << "高度数组: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]" << endl;
    cout << "能接到的雨水总量: " << water << endl << endl;
    
    cout << "=== 算法总结 ===" << endl;
    cout << "1. 双指针：适用于有序数组的查找、滑动窗口问题" << endl;
    cout << "2. BFS：适用于最短路径、层次遍历、多源扩散问题" << endl;
    cout << "3. DFS：适用于回溯、路径搜索、连通性检测问题" << endl;
    cout << "4. 三种算法各有优势，需要根据具体问题选择合适的算法" << endl;
}

int main() {
    demonstrateComprehensive();
    return 0;
}
